Image-representative signals can be digitized, encoded, and subsequently decoded in a manner which substantially reduces the number of bits necessary to represent a decoded reconstructed image without undue or noticeable degradation in the reconstructed image. Image coding is an essential part of many applications such as digital television transmission, video conferencing, facsimile, image database, etc. The simplest technique for this purpose is pulse code modulation (PCM). A PCM system encodes individual pixels of an image in a memory-less way, i.e., it does not use any correlation information between pixels. An improvement over the PCM technique can be made by taking advantage of the correlations between pixels. Predictive coding is one of the techniques based on this principle. It quantizes the difference between a pixel and a prediction of the pixel from its neighbor pixels. Transform coding is another type of technique based on the same principle. In transform coding, a block of data samples is transformed from the image domain to the transform domain using an orthogonal transform, such as the discrete cosine transform (DCT). Two properties of the transform domain coefficients are used. One is that the transform domain coefficients have fewer correlations than the original data samples so that they can be coded individually. The other property is that the energy is packed into a few lower order coefficients so that many higher order coefficients can be either coded with very few bits or discarded.
All of these techniques perform coding on scalars, either in the image domain or in the transform domain. As Shannon's rate-distortion theory indicates, better performance can be achieved by coding vectors instead of scalars. Many vector quantization (VQ) techniques have been developed. As is known in the art, vector quantization is a technique of coding whereby multidimensional vectors are typically represented by a limited number of code words (the collection of code words sometimes being referred to as a "code book"). If, say, there are only 64 words in the code book, they can be distinguished using only 6 bits. In an example of a particular application, these code words may be used to represent, for instance, 2.times.2.times.12 vectors (48 bits). For a given vector to be quantized, the vector quantization technique selects the code word in the code book that is closest (that is, for example, the least different, based on a least squares computation). In the decoding process, the vector represented by the selected code word is used for reconstruction of the original image. For further description vector quantization, reference can be made, for example, to Linde et al., An Algorithm for Vector Quantizer Design, IEEE Transactions on Communications, Vol. Com-28, No. 1, January 1980. Vector quantization had been used on DCT coefficients, but with limitations, since VQ performance is enhanced by the presence of correlation among the components being quantized, and there is inherently low correlation between DCT coefficients. In the U.S. Pat. No. 5,436,985 of Weiping Li, VQ is performed on DCT coefficients using a technique that takes full advantage of attributes of both DCT and VQ.
K-dimensional vector quantization (VQ) is a mapping of a K-dimensional vector x to one of N code-vectors {c(0), c(1), . . . C(N-1)}. It involves encoding and decoding. VQ encoding is a mapping of x to an integer index i : EQU i=E(x)
VQ decoding is a mapping of the index i to a code-vector c(i): EQU c(i)=D(i)
Compression is achieved because transmission or storage of the index i only requires log.sub.2 (N) bits which are much less than the number of bits needed for transmission or storage of this K-dimensional vector x. For a code book without an efficient structure, the VQ encoding mapping of an input vector x to an index i has to be carried out using a look-up table that stores all the code-vectors in a particular order. VQ encoding involves a search of this table to find a code-vector that is closest to the input vector under a distortion measure. The position of this closest code-vector in the table is the index i. In lattice VQ, code-vectors are lattice points in a K-dimensional space. The encoding mapping in lattice VQ does not use a look-up table. The index i can be calculated. For any given input vector x, the encoding process involves two calculations. The first calculation is to find the closest lattice point to the input vector. The second calculation is to find the index of the closest lattice point. The efficiency of labeling lattice points is measured by how many bits are needed to represent the indices of the lattice points within a finite boundary. If log.sub.2 (N) bits are sufficient for representing the indexes of N lattice points within the finite boundary, the labeling method is 100% efficient. Some relatively simple lattices, such as a cubic lattice, can be efficiently labelled using known techniques. However, certain more complex lattices, which are desirable for their excellent densities, pose serious problems of labelling efficiency.
It is among the objects of the present invention to devise a technique and apparatus which is responsive to the limitations of prior lattice vector quantization techniques and which improves labelling efficiency in such techniques.